package main

// Least Frequently Used

import (
	"container/list"
	"fmt"
)

type (
	LFUCache struct {
		nodes         map[int]*list.Element
		lists         map[int]*list.List
		capacity, min int
	}

	node struct {
		key, value, frequency int
	}
)

func Constructor(capacity int) *LFUCache {
	return &LFUCache{
		nodes:    make(map[int]*list.Element),
		lists:    make(map[int]*list.List),
		capacity: capacity,
	}
}

func (c *LFUCache) Get(key int) int {
	value, ok := c.nodes[key]
	if !ok {
		return -1
	}

	currNode := value.Value.(*node)
	c.lists[currNode.frequency].Remove(value)

	currNode.frequency++
	if _, ok := c.lists[currNode.frequency]; !ok {
		c.lists[currNode.frequency] = list.New()
	}
	newList := c.lists[currNode.frequency]
	newNode := newList.PushFront(currNode)
	c.nodes[key] = newNode

	if currNode.frequency-1 == c.min && c.lists[currNode.frequency-1].Len() == 0 {
		c.min++
	}

	return currNode.value
}

func (c *LFUCache) Put(key, value int) {
	if c.capacity == 0 {
		return
	}

	if currVal, ok := c.nodes[key]; ok {
		currNode := currVal.Value.(*node)
		currNode.value = value
		c.Get(key) // update frequency
	} else {
		if c.capacity == len(c.nodes) {
			currList := c.lists[c.min]
			backNode := currList.Back()
			delete(c.nodes, backNode.Value.(*node).key)
			currList.Remove(backNode)
		}

		c.min = 1
		currNode := &node{
			key, value, c.min,
		}
		if _, ok := c.lists[c.min]; !ok {
			c.lists[c.min] = list.New()
		}
		newList := c.lists[c.min]
		newNode := newList.PushFront(currNode)
		c.nodes[key] = newNode
	}
}

func main() {
	capacity := 3
	cache := Constructor(capacity)

	cache.Put(1, 1)
	cache.Put(2, 2)
	cache.Put(3, 3)

	fmt.Println(cache.Get(1))
	fmt.Println(cache.Get(2))
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Put(3, 4)
	fmt.Println(cache.Get(3))
	fmt.Println("------")

	cache.Put(4, 4)
	fmt.Println(cache.Get(1))
	fmt.Println("------")

}
